#ifndef MARCHING_HEAP_H
#define MARCHING_HEAP_H
#include "stdafx.h"

class LevelSetWithIndex
{
public:
	DOUBLE m_phi;
	INT m_i, m_j, m_k;
	LevelSetWithIndex(DOUBLE phi, INT i, INT j, INT k) : m_phi(phi), m_i(i), m_j(j), m_k(k)
	{
	}
};

class MarchingHeap
{
private:
	vector<DOUBLE> dist;
	vector<Index3> indexInHeap;
	UINT m_numX;
	UINT m_numY;
	UINT m_numZ;
	INT*** m_indices;


	UINT parent(UINT i)
	{
		return (i - 1) / 2;
	}
	UINT left(UINT i)
	{
		return 2 * i + 1;
	}
	UINT right(UINT i)
	{
		return 2 * i + 2;
	}
	void exchange (UINT i, UINT j)
	{
		if (i == j)
			return;
		assert(i >= 0 && i < size() && j >= 0 && j < size());
		DOUBLE tmpDist = dist[i];
		Index3 tmpIndex = indexInHeap[i];
		dist[i] = dist[j];
		indexInHeap[i] = indexInHeap[j];
		m_indices[indexInHeap[i].m_i][indexInHeap[i].m_j][indexInHeap[i].m_k] = i;
		dist[j] = tmpDist;
		indexInHeap[j] = tmpIndex;
		m_indices[indexInHeap[j].m_i][indexInHeap[j].m_j][indexInHeap[j].m_k] = j;

	}
	UINT findIndex(INT i, INT j, INT k);
	void minHeapify(UINT i);
	void heapDecreaseKey(UINT i, DOUBLE value);
public:
	MarchingHeap();
	MarchingHeap(UINT numX, UINT numY, UINT numZ);
	~MarchingHeap(void);
	void setSize(UINT numX, UINT numY, UINT numZ);
	void clear();
	BOOL exist(const Index3 index)
	{
		return findIndex(index.m_i, index.m_j, index.m_k) != -1;
	}
	LevelSetWithIndex pop (void);
	void push (const LevelSetWithIndex& elem);
	UINT size (void)
	{
		assert(dist.size() == indexInHeap.size());
		return static_cast<UINT>(dist.size());
	}

};
#endif